//现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其
//中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。 
//
// 如果一个节点的所有子节点为根的 子树 包含的节点数相同，则认为该节点是一个 好节点。 
//
// 返回给定树中 好节点 的数量。 
//
// 子树 指的是一个节点以及它所有后代节点构成的一棵树。 
//
// 
//
// 
//
// 示例 1： 
//
// 
// 输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] 
// 
//
// 输出：7 
//
// 说明： 
// 
// 树的所有节点都是好节点。 
//
// 示例 2： 
//
// 
// 输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]] 
// 
//
// 输出：6 
//
// 说明： 
// 
// 树中有 6 个好节点。上图中已将这些节点着色。 
//
// 示例 3： 
//
// 
// 输入：edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,1
//2],[10,11]] 
// 
//
// 输出：12 
//
// 解释： 
// 
// 除了节点 9 以外其他所有节点都是好节点。 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 10⁵ 
// edges.length == n - 1 
// edges[i].length == 2 
// 0 <= ai, bi < n 
// 输入确保 edges 总表示一棵有效的树。 
// 
//
// Related Topics 树 深度优先搜索 👍 48 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2024-11-15 19:50:00
 * @description 3249.统计好节点的数目
 
 */
 
public class CountTheNumberOfGoodNodes {
    public static void main(String[] args) {
    //测试代码
    CountTheNumberOfGoodNodes fun = new CountTheNumberOfGoodNodes();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 1.建图
        * 2.统计字数的node数目
        * 3.遍历所有子树，如果相等答案+1
        * 4.因为是无向树，所以不知道哪个是父节点
        *
        * */
    List<Integer> [] g;
    int res;
    public int countGoodNodes(int[][] edges) {
        //边的条数，顶点为边+1
        int n=edges.length;
        g=new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            g[i]=new ArrayList<>();
        }
        //无向图
        for (int[] edge : edges) {
            int x=edge[0],y=edge[1];
            g[x].add(y);
            g[y].add(x);
        }
        res=0;
        dfs(0,-1);
        return res;
    }
    //当前节点和父节点father
    private  int dfs(int x,int fa){
        int size=1; //当前节点也算1
        //表示上一个子节点的节点数
        int pre=-1;
        //是否合法
        boolean valid=true;
        for (int y : g[x]) {
            if(y==fa) continue; //不往父节点去
        int subSize=dfs(y,x); //找这个节点的子节点的个数
        if(pre!=-1&&pre!=subSize) valid=false;  // 注意不能 break，其他子树 y 仍然要递归
        size+=subSize;
        pre=subSize;
        }
        //这个节点遍历完了，如果还合法，答案+1
        if(valid) res++;
        return size;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
